package com.zklh.leetcode.interviewTop150;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 串联所有单词的子串
 * author: tongnan
 * date: 2024/8/2
 */
public class Solution30 {
    public List<Integer> findSubstring(String s, String[] words) {
        int step = words[0].length();
        Map<String, Integer> wordToCount = Arrays.stream(words).collect(Collectors.toMap(s1 -> s1, s1 -> 1, Integer::sum));
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < step; i++) {
            int left = i;
            int right = i + words.length * step;
            int current = i;
            // step init
            Map<String, Integer> stepWordToCount = new HashMap<>();
            int balance = words.length;
            if (right > s.length()) break;
            while (current < right) {
                String word = s.substring(current, current + step);
                stepWordToCount.put(word, stepWordToCount.getOrDefault(word, 0) + 1);
                if (wordToCount.containsKey(word) && stepWordToCount.get(word) <= wordToCount.get(word)) {
                    balance--;
                } else {
                    balance++;
                }
                current += step;
            }
            if (balance == 0) {
                result.add(left);
            }

            while (right + step <= s.length()) {
                String leaveWord = s.substring(left, left + step);
                stepWordToCount.put(leaveWord, stepWordToCount.get(leaveWord) - 1);
                if (wordToCount.containsKey(leaveWord)) {
                    if (stepWordToCount.get(leaveWord) >= wordToCount.get(leaveWord)) {
                        balance--;
                    } else {
                        balance++;
                    }
                } else {
                    balance--;
                }
                String comeWord = s.substring(right, right + step);
                stepWordToCount.put(comeWord, stepWordToCount.getOrDefault(comeWord, 0) + 1);
                if (wordToCount.containsKey(comeWord) && stepWordToCount.get(comeWord) <= wordToCount.get(comeWord)) {
                    balance--;
                } else {
                    balance++;
                }
                left += step;
                right += step;
                if (balance == 0) {
                    result.add(left);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution30 solution30 = new Solution30();
        List<Integer> result = solution30.findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"});
        System.out.println(111);
    }
}
